//
// Created by Jisam on 2024/5/26.
//
#include<bits/stdc++.h>
using  namespace  std;
const int MANX = 1e5+5;
int a[MANX];



    int get_idx(int l,int r){
        return l+rand()%(r-l+1);  //采用随机中轴
        // return (l+r)/2;     //采用中间值作为中轴
        // return l;    //采用左端点作为中轴
        // return r;      //采用右端点作为中轴
    }
    void kuaipai(int l,int r,vector<int>& nums){

        if(l>=r) return ;
        int idx=get_idx(l,r);
        int p=nums[idx];
        int i=l,j=r;
        while(i<=j){

            while(i<=j&&nums[i]<p) i++;
            while(i<=j&&nums[j]>p) j--;
            if(i>j) break;
            swap(nums[i++],nums[j--]);
        }
        kuaipai(l,j,nums);
        kuaipai(i,r,nums);
    }
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        kuaipai(0,n-1,nums);
        return nums;
    }

int main(){
    int n  = 8;
    cout << __builtin_ctz(n) <<endl;

    vector<int> a{1,2,4,5,1};
    sortArray(a);
    for(auto  x : a) cout << x << " ";
    return 0;
}